package bm47;

import java.util.PriorityQueue;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/9/19 23:35
 * BM47. 寻找第 K 大
 * https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf?tpId=295&tqId=44581&ru=%2Fpractice%2F02bf49ea45cd486daa031614f9bd6fc3&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    public int findKth (int[] arr, int n, int k) {
        if (n < k) {
            return -1;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 小根堆
        // 先存 k 个数
        int index = 0;
        while (k-- != 0) {
            minHeap.offer(arr[index++]);
        }
        // 迭代
        while (index < n) {
            if (arr[index] >= minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(arr[index]);
            }
            index++;
        }
        return minHeap.peek();
    }
}
